After refining Prim's, let's explore Kruskal's algorithm: an entirely different greedy strategy for finding MSTs that focuses on edges rather than vertices.
- Instead of growing one tree from a start vertex, Kruskal's builds a "forest" of trees that gradually merge.
- First, sort all edges in the graph by weight, from smallest to largest.
- Iterate through the sorted edges, adding an edge to the MST *only if* it connects two disconnected components and doesn't form a cycle.
- The algorithm stops when the MST has $V-1$ edges.
- The main challenge is efficiently detecting cycles, which requires a special data structure.
| Edge | Weight |
|---|---|
| (B, C) | 1 |
| (C, D) | 2 |
| (A, C) | 3 |
| (A, B) | 4 |
| (B, D) | 5 |
| (C, E) | 6 |
| (D, F) | 7 |
| (D, E) | 8 |
| (E, F) | 9 |